package org.example.myleet.p1178;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    /**
     * 82 ms
     * 哈希比较 + 二进制压缩（二进制位运算操作）
     * 思路：先将word进行简化，使用一个32位的整数存储word中每一个字母出现的情况，相同的字母出现情况合并到一个频数哈希表中
     * 然后针对puzzle进行子集遍历，之所以对puzzle进行子集遍历，是因为puzzle的长度固定是7，可以遍历puzzle的所有组合情况
     * 当puzzle中的其中一众字母组合在频数哈希表中出现时，即找到相应的单词频数，添加到答案中，最后输出答案
     */
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        int wn = words.length, pn = puzzles.length;
        HashMap<Integer, Integer> wordMap = new HashMap<>();
        for (int i=0; i<wn; i++) {
            //word初始化，出现字母的位置标记为1
            int wl = words[i].length();
            int wordHash = 0;
            for (int j=0; j<wl; j++) {
                int c = words[i].charAt(j) - 'a';
                wordHash = setBit(wordHash, c);
            }
            if (Integer.bitCount(wordHash) > 7) {
                //如果出现1的位数大于7，则不可能是谜底，忽略
                continue;
            }
            //统计频数
            wordMap.put(wordHash, wordMap.getOrDefault(wordHash, 0) + 1);
        }
        List<Integer> ans = new ArrayList<>(pn);
        for (int i=0; i<pn; i++) {
            //针对某个puzzle遍历子集
            int puzzleHash = 0;
            int count = 0;
            int pl = puzzles[i].length();
            for (int j=1; j<pl; j++) {
                //除第1位字母以外，其余各位字母的位置记为1
                int c = puzzles[i].charAt(j) - 'a';
                puzzleHash = setBit(puzzleHash, c);
            }
            int subset = puzzleHash;
            //除第1位字母
            int c0 = puzzles[i].charAt(0) - 'a';
            do {
                //s是某一种情况，subset是某一种第一位不是1情况，因此先将第1位变成1（题目要求谜底必须包含puzzle的第1位字母）
                int s = setBit(subset, c0);
                if (wordMap.containsKey(s)) {
                    //找到一种单词的字母组合，则加上相应的频数
                    count += wordMap.get(s);
                }
                //！以下是难点
                //更新子集组合，先-1，则最右边的1会右移1位，相当于整个由1组成的组合的最右边的1往右移动1位
                //然后整个数和puzzleHash做与运算之后，由于其他1位不受影响，最右边的1往右移动了，与原来的1位置不匹配，就会被抹去
                //结果就是1组合里最右边的1一直往右移动直到消失，逐个1往右移动最终就可以遍历所有情况
                //例如：原有组合010010110 -> - 1
                //=> 010010101 -> & 010010110
                //=> 010010100（相当于最右边的1消掉了）
                subset = (subset - 1) & puzzleHash;
            } while (subset != puzzleHash);
            ans.add(count);
        }
        return ans;
    }

    /**
     * 相当于先找出100000（i个0），然后与运算使得该位置如果是0，返回0，如果是1，则返回1后接i个0的二进制数（>1）
     */
    private int getBit(int num, int i) {
        return (num & (1 << i));
    }

    /**
     * 将第i位变成1，相当于先找出100000（i个0），然后或运算使得该位置如果是0，变成1，如果是1，则还是1
     */
    private int setBit(int num, int i) {
        return (num | (1 << i));
    }
}
